package com.Q16;

public class Q16_02 {
    public static void main(String[] args) {
//        WordsFrequency wordsFrequency = new WordsFrequency(new String[]{"i", "have", "an", "apple", "he", "have", "a", "pen"});
        WordsFrequency wordsFrequency = new WordsFrequency(new String[]{"an","a"});
        wordsFrequency.get("you"); //返回0，"you"没有出现过
        wordsFrequency.get("have");// 返回2，"have"出现2次
        wordsFrequency.get("an"); //返回1
        wordsFrequency.get("apple"); //返回1
        wordsFrequency.get("pen"); //返回1
    }
}

class WordsFrequency {

    Node root = new Node();

    // hashmap、前缀树
    public WordsFrequency(String[] book) {
        // 构建前缀树
        for (String word : book) {
            Node cur = root;
            for (int i = 0; i < word.length(); i++) {
                int index = word.charAt(i) - 'a';
                if (cur.children[index] == null) {
                    cur.children[index] = new Node();
                }
                cur = cur.children[index];
            }
            cur.frequency++;
        }
    }

    public int get(String word) {
        Node cur = root;
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a';
            if (cur.children[index] == null) return 0;
            cur = cur.children[index];
        }
        return cur.frequency;
    }

}

class Node {
    Node[] children;
    int frequency;

    Node() {
        children = new Node[26];
        frequency = 0;
    }
}